package leetcode;

/**
 * @author Liangyaoyun
 */
public class leetCode105 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){
        }
        TreeNode(int val){
            this.val=val;
        }
        TreeNode(int val,TreeNode left,TreeNode right){
            this.val=val;
            this.left=left;
            this.right=right;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root=new TreeNode(preorder[0]);
        if (preorder.length==1){
            return root;
        }
        return BuildTree(preorder,0, preorder.length-1,inorder,0,inorder.length-1 );
    }
    public TreeNode BuildTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){
        //递归出口
        if (preStart>preEnd){
            return null;
        }

        //找到根节点
        TreeNode root=new TreeNode();
        root.val=preorder[preStart];


        //找到根节点的下标
        int rootIndex=findRoot(inorder,root,inStart,inEnd);


        //根据中序序列的下标位置和当前的递归层次
        //计算出左右子树的长度
        int leftLength=rootIndex-inStart;
        int rightLength=inEnd-rootIndex;

        root.left=BuildTree(preorder,preStart+1,leftLength+preStart,inorder,inStart,rootIndex-1);
        root.right=BuildTree(preorder,leftLength+preStart+1,preEnd,inorder,rootIndex+1,inEnd);

        return root;
    }

    public int findRoot(int[] inorder,TreeNode root,int inStart ,int inEnd){
        for (int i = inStart; i <=inEnd; i++) {
            if (root.val==inorder[i]){
                return i;
            }
        }
        return -1;
    }
}
